1. Field of the Invention
The present invention relates to programmable logic devices, and more specifically to a method for mapping product terms (P-terms) into complex programmable logic devices in which all of the P-term elements of a function block are routable to each macrocell of the function block.
2. Background Art
Programmable logic devices (PLDs) are a class of integrated circuits (ICs) which can be programmed by a user to emulate various logic functions. Logic designers typically use PLDs to implement control logic in electronic systems because they are relatively easy to program, and often can be reprogrammed to update the emulated logic function. This makes their use in an electronic system's design phase less costly than custom hardwired or "application specific" integrated circuits (ASICs).
One major class of PLDs includes a set of input pins, a programmable AND plane connected to the input pins, an OR plane connected to outputs of the AND plane and a set of output pins connected to outputs of the OR plane. The AND plane provides a matrix of programmable connections where each column connects to an input pin and each row forms an output of the AND plane, called a product term (P-term) element, which is transmitted to the OR plane. The OR plane may be programmable, such that each P-term element is connectable to columns leading to different output pins, in which case the PLD is called a programmable logic array (PLA). Alternatively, the OR plane may be fixed, such that each P-term element is assigned to a particular output pin, in which case the PLD is called a programmable array logic (PAL) device.
PLAs and PALs contain two levels of logic (AND and OR) and are capable of implementing logic functions that are representable in "sum-of-products" form. The sum-of-products form of a logic function includes a set of P-terms which are collectively "ORed" together to produce the function's output signal. Such a logic function is represented in a PLD by programmed connections in the AND plane and OR plane. Each P-term element has a programmable input connection in the AND plane to each input pin and produces a single output value representing the logical AND or "product" of the connected inputs. Usually, both the original input pin value and its complement are available for connection to a P-term element. Each output has a programmable P-term element connection in the OR plane and produces an output value representing the logical OR or "sum" of the connected P-term elements.
These early PLDs were well-received by logic designers. However, as logic functions grew increasingly larger and more complex, logic designers were required to wire together two or more small PLDs to provide sufficient logic capacity. Although this process was tolerated during development and testing, it increased the cost and size of production units. This generated a demand for PLDS with increasingly larger logic capacity.
To meet the ever-increasing demand for greater capacity, PLDs with increasingly complex architectures have been developed. One popular complex PLD type, known as complex programmable logic devices (CPLDs), includes two or more "function blocks" connected together and to input/output (I/O) resources by an interconnect matrix such that each of the function blocks communicates with other function blocks of the CPLD through the interconnect matrix. Each function block of the CPLD is structured like the two-level PLDs, described above. In effect, these CPLDs incorporate several early PLDs and associated connection circuitry onto a single integrated circuit. This provides a circuit designer the convenience of implementing a complex logic function using a single IC.
Each function block of an early CPLD typically includes an AND array and a set of macrocells. The input signals of the AND array are received from the interconnect matrix, and each of the P-term elements generated by the AND array is assigned to one of the macrocells such that a specific number of P-term elements are assigned to each macrocell. Each macrocell includes an OR gate which is programmable to receive one or more of the assigned P-term elements, and also to receive a sum-of-products term from an adjacent macrocell of the function block (see the discussion below regarding the "chaining" process). The OR gate of each macrocell produces a sum-of-products term which is either Transmitted to output circuitry of the CPLD, fed back to the interconnect matrix, or is transmitted to an adjacent macrocell (by the "chaining" process, discussed below). To simplify the following discussion, it is assumed that the macrocells of each function block are arranged side-by-side in a row such that a centrally-located macrocell has at least one macrocell located on its "right", and one macrocell located on its "left".
The macrocells of these early CPLDs are programmable to share their assigned P-term elements with one adjacent macrocell by a process referred to herein as "chaining". As mentioned above, an OR gate of each ("first") macrocell receives a specific number of P-term Elements (e.g., five) from the AND array, and is also programmable to receive a sum-of-products term from an adjacent ("second") macrocell (e.g., the macrocell located to the immediate "left" of the first macrocell). To implement a function requiring more that the specific number of P-term elements (e.g., eight P-term elements), the second macrocell is programmed to transmit three of the P-term elements as a sum-of-products term to the OR gate of the first macrocell, thereby increasing the number of P-term elements utilized by the first macrocell to eight. By this process, the first and second macrocells are "chained" together to implement functions made up of a large number of P-terms. Even larger functions are implemented by "chaining" additional macrocells to the first and second macrocells in the manner described above.
A restriction of these early CPLDs is that the "chaining" process is only available in one "direction". For instance, P-term elements are only transmitted "right" from the second macrocell to the first macrocell; P-term elements cannot be transmitted "left" from the first macrocell to the second macrocell. This reduced the programming "flexibility" of these early CPLDs because, given a multiple P-term function whose output is assigned to the first macrocell, the only available source of additional P-tern elements is to the "left" of the first macrocell. If another function is already implemented by the second macrocell, the programming process fails because the first macrocell cannot be "chained" to receive P-term elements from a macrocell which is located to the "right" of the first macrocell.